import sys
import numpy as np
import time



car_per_sec = 30# can't higher than 21
interval_time = 10

def read_inf(filename):
    out_list = []
    with open(filename, 'r') as f:
        while True:
            line = f.readline()
            if not line:
                break
            if line[0] == '#':
                continue
            
            out0 = line.replace('(', '')
            out0 = out0.replace(')', '')
            out0 = out0.strip()
            out1 = [int(i) for i in out0.split(',')]

            out_list.append(out1)
    return out_list


def delete(li, index):
    li_back = li[:index] + li[index+1:]
    return li_back


def map_graph(cross, road):
    """
    input: cross, cross_inf; road, road_inf
    """
    a = len(cross)
    graph = {}
    #生成对角线全0 的矩阵
    array_dis = np.zeros([a, a]) + 1000000 - 1000000 * np.eye(a)
    array_road = np.zeros([a, a])
    road_list = []
    cross_list  = []

    for i in range(len(road)):
        road_list.append(road[i][0])
    
    for i in range(len(cross)):
        cross_list.append(cross[i][0])

    for i in road:
        name, length, channel, speed_lim, start_id, end_id, is_dux = i ###### is_dux = i[6]???
        start_id -= 1
        end_id -= 1

        if is_dux == 1:
            array_dis[start_id][end_id] = array_dis[end_id][start_id] = length
            array_road[start_id][end_id] = array_road[end_id][start_id] = name
        else:
            array_dis[start_id][end_id] = length
            array_road[start_id][end_id] = name
    array_loss = array_dis

    return graph, array_dis, array_road, array_loss, cross_list, road_list


def record_road(batch, road_use_list, road_percent_list, road_id_bias):
    for i in batch:
        for j in i[2:]:
            road_use_list[j-road_id_bias] += 1
    
    sum_use = sum(road_use_list)
    a = len(road_use_list)
    for i in range(a):
        road_percent_list[i] = road_use_list[i] / sum_use
    
    return road_use_list, road_percent_list


def speed_split(car_inf):
    #速度相同的车划分在一起
    max_speed = 0
    car_divide_speed = []

    # split car by speed, car_divide_speed[k] means car speed as k+1
    for i in car_inf:
        if i[3] > max_speed:
            max_speed = i[3]
    for i in range(max_speed):
        car_divide_speed.append([])
    for i in car_inf:
        car_divide_speed[i[3] - 1].append(i[0])
    output_dic = {}
    for i in range(max_speed):
        output_dic[i+1] = car_divide_speed[i]
    return output_dic


# TODO: jv li jin de xian fa che
# calculate start time of each car by position
def time_split(group, car_inf, car_per_sec, time, interval_time, speed, car_id_bias, car_position):

    cur_batch = []
    group_divide_time = []
    group_len = len(group)
    group_position = []
    #每秒21辆，间隔10秒
    batch_num = int(group_len / car_per_sec / interval_time )+1

    # for i in group:
    #     group_position.append(car_position[i])

    for i in range(batch_num):
        cur_batch = []
        for j in range(car_per_sec * interval_time):
            try: 
                cur_batch.append(group.pop())
            except:
                break
        group_divide_time.append(cur_batch)
    
    # for k in range(max_speed):

    #     delta = 1 + (k-1) * 0.01
    #     cur_group = car_divide_speed[-k]
    #     if not cur_group:
    #         continue
    #     cur_amount = len(cur_group)

    return group_divide_time


def dijkstra_minpath(start, end, matrix):
    inf = 1000000
    length = len(matrix)
    path_array = []
    temp_array = []
    path_array.extend(matrix[start])
    temp_array.extend(matrix[start])
    temp_array[start] = inf
    already_traversal = [start]
    path_parent = [start] * length

    i = start
    flag=0
    while(i != end):
        path = []
        if min(temp_array)!=1000000:
            i = temp_array.index(min(temp_array))
            temp_array[i] = inf
            path.append(i)
            k = i
            while (path_parent[k] != start):
                path.append(path_parent[k])
                k = path_parent[k]
            path.append(start)
            path.reverse()
            already_traversal.append(i)
            for j in range(length):
                if j not in already_traversal:
                    if (path_array[i] + matrix[i][j]) < path_array[j]:
                        path_array[j] = temp_array[j] = path_array[i] + matrix[i][j]
                        path_parent[j] = i
            # print(start, end,path)
            flag=1
        else:
            flag = 0
            break
    return path,flag



# update 3.19: change all to batch planning
# car_id_bias: car_id0 - 0; batch: [car_id1, car_id2, ...]
def cal_car_path(unfinish,count_time_top0,map_loss_array1,road_inf,road_id_bias,map_loss_array, map_road_array, car_inf, batch, car_id_bias, time):
    batch_len = len(batch)
    path = []
    path_road_time = []
    road_ids = []

    temp=0
    for i in batch:
        #得到数组的index
        car_id = i - car_id_bias
        temp=temp+1
        # print ('......',time,temp)
        path,flag = dijkstra_minpath(car_inf[car_id][1]-1, car_inf[car_id][2]-1, map_loss_array)
        if flag:
            path_center = []
            a = len(path)
            path_center.append(car_inf[car_id][0])
            path_center.append(max(car_inf[car_id][4], time))
            for j in range(a-1):
                road_id=int(map_road_array[path[j]][path[j + 1]])
                path_center.append(road_id)
                road_ids.append(road_id)

            path_road_time.append(path_center)
        else:
            unfinish.append(i)

    import pandas as pd
    count_time = pd.DataFrame({'road': road_ids})
    count_time = count_time.groupby('road').size().reset_index()
    count_time.columns = ['road', 'time']
    # count_time = count_time.sort_values(by='time',ascending=False).reset_index(drop=True)
    count_time_top=[]
    # for dropnum in [1,3,5,7,9]:
    #     count_time_top.append(count_time.ix[dropnum,'road'])
    # count_time_top = count_time[0:5]['road'].values.tolist()



    # for road_id in count_time_top0:
    #     road_index = road_id - road_id_bias
    #     # 这他妈这里有bug呀 j
    #     name, length, channel, speed_lim, start_id, end_id, is_dux = road_inf[road_index]  ###### is_dux = i[6]???
    #     start_id -= 1
    #     end_id -= 1
    #
    #     if is_dux == 1:
    #         map_loss_array[start_id][end_id] = map_loss_array[end_id][start_id] = map_loss_array1[start_id][end_id]
    #     else:
    #         map_loss_array[start_id][end_id] = map_loss_array1[start_id][end_id]

    for road in road_inf:

        name, length, channel, speed_lim, start_id, end_id, is_dux = road  ###### is_dux = i[6]???
        road_index = name - road_id_bias
        road_loss = 1000000
        start_id -= 1
        end_id -= 1
        temptime=count_time[count_time['road'] == name]['time'].values
        #tiao
        if temptime > (0.7 * length*channel):
            count_time_top.append(name)
            if is_dux == 1:
                map_loss_array[start_id][end_id] = map_loss_array[end_id][start_id] = road_loss
            else:
                map_loss_array[start_id][end_id] = road_loss
        else:
            if is_dux == 1:
                map_loss_array[start_id][end_id] = map_loss_array[end_id][start_id] = length
            else:
                map_loss_array[start_id][end_id] = length
    count_time_top0 = count_time_top.copy()

    print('update:', count_time_top0)
    return unfinish,path_road_time,count_time_top0




def update_loss(map_loss_array1,array_loss, array_dis, road_inf, speed):
    for i in road_inf:
        _, length, channel, speed_lim, start_id, end_id, is_dux = i
        start_id -= 1
        end_id -= 1
        # 可调
        loss = length * (1 + 2/channel/+1/speed+1/speed_lim+4/length)

        if array_loss[start_id][end_id]!=1000000:
            if is_dux == 1:
                array_loss[start_id][end_id] = array_dis[end_id][start_id] = loss
                map_loss_array1[start_id][end_id] = map_loss_array1[end_id][start_id] = loss
            else:
                array_loss[start_id][end_id] = loss
                map_loss_array1[start_id][end_id] = loss

    return array_loss,map_loss_array1

def main():

    car_path = sys.argv[1]
    road_path = sys.argv[2]
    cross_path = sys.argv[3]
    answer_path = sys.argv[4]


    # car_path = 'E:/car.txt'
    # road_path = 'E:/road.txt'
    # cross_path = 'E:/cross.txt'
    # answer_path = 'E:/answer.txt'

    # (结点id,道路id,道路id,道路id,道路id)
    cross_inf = read_inf(cross_path)
    # (道路id，道路长度，最高限速，车道数目，起始点id，终点id，是否双向)
    road_inf = read_inf(road_path)
    # (id,始发地,目的地,最高速度,出发时间)
    car_inf = read_inf(car_path)

    _, map_dis_array, map_road_array, map_loss_array, _, _ = map_graph(cross_inf, road_inf)
    car_divide_speed = speed_split(car_inf)

    time = 0
    #起始车号
    car_id_bias = car_inf[0][0]
    road_id_bias = road_inf[0][0]
    car_position = {}
    answer = []
    speed_list = []
    road_use_list = road_percent_list = [0] * len(road_inf)

    # 1. divide by speed
    # 2. calculate time by position (TODO)
    # 3. loop: calculate path ; record road ; update map (TODO)
    for speed in car_divide_speed:
        speed_list.append(speed)
    speed_list.reverse()

    map_loss_array1=map_loss_array.copy()
    count_time_top0=[]
    for speed in speed_list:
        cur_group = car_divide_speed[speed]
        if not cur_group:
            continue 
        #210一个批次，carid
        group_divide_time = time_split(cur_group, car_inf, car_per_sec, time, interval_time, speed, car_id_bias, car_position)
        unfinish = []
        for batch in group_divide_time:
            #车号，发车时间，道路

            unfinish,batch_path_time,count_time_top0 = cal_car_path(unfinish,count_time_top0,map_loss_array1,road_inf,road_id_bias,map_loss_array, map_road_array, car_inf, batch, car_id_bias, time)
            time += interval_time
            answer += batch_path_time
            # road_use_list, road_percent_list = record_road(batch_path_time, road_use_list, road_percent_list, road_id_bias)
            map_loss_array,map_loss_array1 = update_loss(map_loss_array1,map_loss_array, map_dis_array, road_inf, speed)

        print('lenunfinish:',len(unfinish))
        unfinish2 = unfinish.copy()
        while(len(unfinish2)!=0):
            unfinish2 = []
            unfinish2, batch_path_time, count_time_top0 = cal_car_path(unfinish2, count_time_top0, map_loss_array1, road_inf,
                                                                      road_id_bias, map_loss_array, map_road_array, car_inf,
                                                                      unfinish, car_id_bias, time)
            time += interval_time
            answer += batch_path_time
            unfinish=unfinish2.copy()
            print('lenunfinish2:', len(unfinish2))
    # path_road = all_car_path(map_loss_array, map_road_array, car_inf)
    # car_time_sche = time_split(car_inf, car_per_sec, path_road)
    # answer = combine_time_path(car_inf, car_time_sche, path_road)
    # answer = all_car_path(map_dis_array, map_road_array, car_inf, car_time_sche)
    
    with open(answer_path, 'w') as fp:
        fp.write('\n'.join(str(tuple(x)) for x in answer))


if __name__ == "__main__":
    main()